1. Field of the Invention
The present invention generally relates to digital halftoning techniques for printing a picture on a two-dimensional medium in printers. This invention is a method and apparatus to construct calibrated dither masks adaptable to most printers in such a way that the threshold values can be adapted to the printer so that the printer can print the originally intended number of distinct tone (e.g., grey or color) levels. This adaptation can be done computationally so that the time it takes is not prohibitive. The present invention builds on and improves upon previous techniques because the resulting calibrated dither mask is such that there is no need for a tone reproduction curve in the halftoning process.
2. Background Description
Most printers can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance. In fact, the rest of the discussion will be specialized to the case of grey scale images and their rendering by black and white printers to facilitate the presentation.
We will be concerned with bilevel, fixed pixel size printers (for instance laser printers). Such printers are usually considered to have two fundamental characteristics: the pixel density, say d dpi (dots per inch), which can be interpreted as telling us that the ideal pixel size is 1/d inches by 1/d inches (where d typically varies from about 300 to about 3000) and the mechanical dot gain which is a number describing how much bigger the printed dot is compared to a perfect 1/d by 1/d square.
Consider now some grey scale image to be printed with a digital printer. We assume that this image is of size h by v, where h and v are expressed in inches to be consistent with the unit used in the dot resolution description. It is then convenient to interpret this image as a matrix I of size H=hxc3x97d by V=vxc3x97d in the following way:
One thinks of the image as covered by little squares of size 1/d by 1/d called pixels.
Then each pixel p, can be designated by its horizontal ordering number i (say from left to right) and its vertical ordering number j (say from top to bottom); thus, the location of p is specified by the pair (i,j).
To the pixel (i,j) one assigns the value val between 0 and 1, where 0 corresponds to white, 1 corresponds to black, and more generally, val corresponds to the grey level of this particular pixel.
Given a matrix such as I, a digital halftoning algorithm will associate to it a H by V printing decision matrix M whose entries M(i,j) are either 0 or 1, where 0 now means that no dot will be printed by the digital printer at pixel (i,j), while a 1 means that a dot is to be printed.
One of most frequently used methods of preparing such a matrix M, consists in using some dither mask D. Such a mask, defined either in hardware or in software, can be thought of as a matrix of numbers. We assume that D is a W by L matrix with entries between 0 and 1. One uses D to generate M by setting
M(ij)=1 if I(i,j) greater than D(i mod W,j mod L),
M(i,j)=0 if I(i,j) less than D(i mod W,j mod L).
In these formulas, the mod notation should be understood as follows: If a and b are two integers, a mod b is the remainder of the division of a by b. The formulas for M justify the name of threshold levels for the entries of D. We denote by T the set of threshold values of D. The number of distinct threshold values determines the number of distinct grey levels which could be printed with D on a printer with perfect 1/d by 1/d pixels. In fact, if the image I is some uniform grey level g1, only those pixels with D(i mod W,j mod L) less than g get printed. As a consequence, except in the case when D is designed for a specific printer, since the dot gain is unknown, one chooses the threshold values to be evenly distributed between 0 and 1. The book xe2x80x9cDigital Halftoningxe2x80x9d by R. Ulichney (MIT Press Cambridge, Mass. 1987), which is a general reference on digital halftoning contains several methods of generating dither masks. In the patent application xe2x80x9cClustered Aperiodic Maskxe2x80x9d by G. R. Thompson et al., Ser. No. 08/943,881, filed Oct. 3, 1997, a method is disclosed to generate a dither mask which can have a large number of grey levels.
To calibrate the printer for printer characteristics such as dot gain, prior art uses a tone reproduction curve (TRC), a function which describes the relationship between the intended grey and the actual grey printed by the printer. This is usually implemented as a look-up table. For instance, in U.S. Pat. No. 5,309,177 issued to Shoji et al., a TRC is used as a look-up table to correct the image data to be printed. In U.S. Pat. No. 5,347,369 issued to Harrington, a method is disclosed to obtain the TRC without special equipment.
Problems to Be Solved
If the dither mask D is used on a printer P, because of the way P prints dots, the printed version of each individual grey level will be different from what is intended. In prior art, one usually corrects this problem by using a (printer dependent) tone reproduction curve T which describes the relationship between the grey that you instruct the printer to print and the grey the printer actually prints. For example, instructing the printer to print a uniform patch of grey level g could result in a patch with grey level gxe2x80x2. The relation between various values of g and corresponding values gxe2x80x2 is embodied in a tone reproduction curve, T(g), which specifies the output grey level for a given input grey level. In other words, T(g)=gxe2x80x2. The tone reproduction curve is then used either to transform the grey level at each (i,j) before it is compared to the threshold value D(i,j), or to transform the entries of D. This can result in the number of distinct grey levels which can be printed being less than the number of distinct values in the original matrix D. Specifically, this happens when D consists entirely of a sequence of k consecutive integers from 1 through k, and T is a non-linear mapping onto 1 through k. Then some input integers are mapped onto the same output integer and the number of distinct output integers is less than the number of input integers, k.
It is therefore an object of the invention to provide a method and apparatus to construct calibrated dither masks adaptable to most printers in such a way that the threshold values can be adapted to printer P so that printer P can print the originally intended number of distinct tone levels. This adaptation can be done computationally so that the time it takes is not prohibitive. Furthermore, the resulting calibrated dither mask is such that there is no need for a tone reproduction curve in the halftoning process.
Several methods are available which allows one to compute an approximation N1(M, P) of the image a printer P will print given the matrix M. If a dither mask is to be prepared to print d distinct grey levels with essentially any printer P, we will prepare a master mask D0 with some number d0 of threshold levels, where d0 is significantly larger than d. For each of these threshold levels, t, one can easily compute the matrix M(t) corresponding to a constant grey level t. In other words, we print a patch of constant input grey level t of the size of M using the dither matrix D0. As mentioned above, one deduces easily from there the matrix N1(M(t), P) if the specificity of P is known in a convenient way. We then select the dxe2x88x921 values of t which give the closest approximations to the grey levels 1/d, 2/d, . . . , (dxe2x88x921)/d, and call t1, t2, . . . , tdxe2x88x921 the corresponding values of t in increasing order.
In other words, we print patches for all d0 distinct grey values in D0 and measure the output. White will be considered xe2x80x9c0xe2x80x9d and pure black is considered xe2x80x9c1xe2x80x9d, with d0xe2x88x921 values in between. We then find which of those doxe2x88x921 values is closest to 1/d, 2/d, . . . , (dxe2x88x921)/d. We then select these to be the threshold values ti.
The matrix D0 is then transformed to a matrix Dp adapted to the printer P by setting             D      p        ⁡          (              i        ,        j            )        =            min      k        ⁢          (                        t          k                ⁢                              "LeftBracketingBar"                                          t                k                            ≥                                                D                  0                                ⁡                                  (                                      i                    ,                    j                                    )                                                      )                    .                    
Note that Dp contains fewer values than D0, and intermediate values in D0 are set to the next highest values of tk in the sequence t1, t2, . . . , tdxe2x88x921. Some of the main features of the present invention are:
1. The resulting, calibrated halftoning system allows a predetermined number of grey levels to be printed.
2. The resulting calibrated halftoning system utilizes a simple dither algorithm without the need for a tone reproduction curve.